/*this program aims for providing the algrithom of merge sort

   */
#include<stdio.h>
#include<stdlib.h>
void merge(int *arr,int left,int mid,int right){
	int i=left;
	int j=mid;
	int* tmp=(int*)malloc((right-left)*4);
	int idx=0;
	while(i<mid&&j<right){
		if(arr[i]<arr[j]){
			tmp[idx]=arr[i];
			i++;
		}else{
			tmp[idx]=arr[j];
			j++;
		}
		idx++;
	}
	while(i<mid){
		tmp[idx++]=arr[i++];
	}
	while(j<right){
		tmp[idx++]=arr[j++];
	}
	for(int i=0;i<idx;i++){
		arr[left+i]=tmp[i];
	}
	free(tmp);
}




void mergeSort(int *arr,int left,int right){
	if(right-left<=1){
		return;
	}
	int mid=(left+right)/2;
	mergeSort(arr,left,mid);
	mergeSort(arr,mid,right);
	merge(arr,left,mid,right);
}




int main(){
	int* arr=(int*)malloc(10*4);
	arr[0]=10;
	arr[1]=9;
	arr[2]=8;
	arr[3]=7;
	for(int i=0;i<4;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
	mergeSort(arr,0,4);
	for(int i=0;i<4;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
	return 0;
}
